// [75]颜色分类
struct Solution;

//leetcode submit region begin(Prohibit modification and deletion)
impl Solution {
    pub fn sort_colors(nums: &mut Vec<i32>) {
        let mut left = 0;
        let mut right = nums.len() - 1;
        let mut mid = 0;
        while mid <= right {
            while left < nums.len() && nums[left] == 0 {
                left += 1;
            }
            while right > 0 && nums[right] == 2 {
                right -= 1;
            }
            if mid > left && nums[mid] == 0 {
                let temp = nums[mid];
                nums[mid] = nums[left];
                nums[left] = temp;
            } else if mid < right && nums[mid] == 2 {
                let temp = nums[mid];
                nums[mid] = nums[right];
                nums[right] = temp;
            } else {
                mid += 1;
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

#[test]
fn main() {
    let mut nums = vec![2, 0, 2, 1, 1, 0];
    Solution::sort_colors(&mut nums);
    assert_eq!(nums, vec![0, 0, 1, 1, 2, 2]);
    let mut nums = vec![2, 0, 1];
    Solution::sort_colors(&mut nums);
    assert_eq!(nums, vec![0, 1, 2]);
    let mut nums = vec![0, 0];
    Solution::sort_colors(&mut nums);
    assert_eq!(nums, vec![0, 0]);
    let mut nums = vec![1, 0];
    Solution::sort_colors(&mut nums);
    assert_eq!(nums, vec![0, 1]);
    let mut nums = vec![1, 2, 0];
    Solution::sort_colors(&mut nums);
    assert_eq!(nums, vec![0, 1, 2]);
}
